package com.chapter10;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.Stack;

public class Tree {

	Tnode root;
	int val=0;
	public Tree(){
		
	}
	public Tree(Tnode root) {
		super();
		this.root = root;
	}

	public void levelOrderTraversal(Tnode root){
		List<Tnode> q= new ArrayList<Tnode>();
		q.add(root);
		int curlevel=1;
		int newlevel=0;
		while(!q.isEmpty()){
			Tnode cur=q.remove(0);
			System.out.print(cur.value+ " ");
			curlevel--;
			if(cur.left!=null){
				q.add(cur.left);
				newlevel++;
			}
			if(cur.right!=null){
				q.add(cur.right);
				newlevel++;
			}
			if(curlevel==0){
				System.out.println();
				curlevel=newlevel;
				newlevel=0;
			}
		}
	}

	public void levelOrderTraversal2(Tnode root){
		List<Tnode> q= new ArrayList<Tnode>();
		q.add(root);
		q.add(null);
		while(q.size()>1){
			Tnode cur=q.remove(0);
			System.out.print(cur.value+ " ");
			if(cur.left!=null)q.add(cur.left);
			if(cur.right!=null)q.add(cur.right);
			if(q.get(0)==null){
				System.out.println();
				q.remove(0);
				q.add(null);
			}
		}
	}
	public void inOrderTraversal(Tnode current){
		if(current==null)
			return;
		inOrderTraversal(current.left);
		System.out.print(current.value+" ");
		inOrderTraversal(current.right);
	}
	public void postOrderTraversal(Tnode current){
		if(current==null)
			return;
		postOrderTraversal(current.left);
		postOrderTraversal(current.right);
		System.out.print(current.value+" ");
	}

	public void inOrderTraversalIterative(){
		List<Tnode> s=new ArrayList<Tnode>();
		s.add(root);
		Tnode cur=root;
		while(!s.isEmpty()){
			while(cur!=null){
				s.add(cur.left);
				cur=cur.left;
			}

			s.remove(s.size()-1);
			if(!s.isEmpty()){
				cur=s.remove(s.size()-1);
				System.out.print(cur.value+ " ");
				cur=cur.right;
				s.add(cur);
			}
		}
	}

	public List<Integer> postOrderTraversalIterative() {
        List<Tnode> s=new ArrayList<Tnode>();
        List<Integer> post=new ArrayList<Integer>();
		Set<Tnode> set=new HashSet<Tnode>();
		s.add(root);
		Tnode cur=root;
		while(!s.isEmpty()){
			while(cur!=null && !set.contains(cur)){
				s.add(cur);
				set.add(cur);
				cur=cur.left;
			}
			
			if(s.get(s.size()-1)==null)s.remove(s.size()-1);
			if(s.isEmpty())break;
			cur=s.get(s.size()-1);
			if(cur.right!=null && !set.contains(cur.right)){
				cur=cur.right;
			}
			else{
				Tnode temp=s.remove(s.size()-1);
				post.add(temp.value);
				if(s.isEmpty())break;
				cur=s.get(s.size()-1);
			}
		}
		if(!post.isEmpty())post.remove(post.size()-1);
		return post;
    }
	
	public void incrementNodeCount(Tnode current){
		while(current.parent!=null){
			if(current.parent.left==current)
				current.parent.leftNodes++;
			else
				current.parent.rightNodes++;
			current=current.parent;
		}
	}

	
	public void decrementNodeCount(Tnode current){
		while(current.parent!=null){
			if(current.parent.left==current)
				current.parent.leftNodes--;
			else
				current.parent.rightNodes--;
			current=current.parent;
		}
	}

	public int findMaxDepth(Tnode node){
		if(node==null)
			return 0;
		return Math.max(findMaxDepth(node.left),findMaxDepth(node.left))+1;
	}
	
	public int findMinDepth(Tnode node){
		if(node==null)
			return 0;
		return Math.min(findMaxDepth(node.left),findMaxDepth(node.left))+1;
	}
	
	public boolean checkBalanced(Tnode node){
		return (findMaxDepth(node) -findMinDepth(node)<=1);
	}
	
	public int findMaxDepthPost(Tnode node){
		if(node==null)
			return 0;
		int leftHeight=findMaxDepthPost(node.left)+1;
		int rightHeight=findMaxDepthPost(node.right)+1;
		return Math.max(leftHeight, rightHeight);
	}
	
	public int findMinDepthPost(Tnode node){
		if(node==null)
			return 0;
		int leftHeight=findMinDepthPost(node.left)+1;
		int rightHeight=findMinDepthPost(node.right)+1;
		
		return Math.min(leftHeight, rightHeight);
	}
	
	public boolean checkBalancedPost(Tnode node){
		return (findMaxDepthPost(node) -findMinDepthPost(node)<=1);
	}
	
	/*
	 * find kth unbalanced. wrks from the bottom.
	 */
	public NodeInfo findNumNodes(Tnode node,int k){
		if(node==null)
			return new NodeInfo(node,0,-1,-1);
		NodeInfo left=findNumNodes(node.left,k);
		NodeInfo right=findNumNodes(node.right,k);
		if(left.max==-1)
			return left;
		if(right.max==-1)
			return right;
		if(Math.abs(right.max-left.max)>k)
		{
			return new NodeInfo(node,-1,-1,-1);
		}
		return new NodeInfo(node,left.max+right.max+1,-1,-1);
	}
	
	/*
	 * check if mirror image
	 */
	public boolean checkMirror(Tnode l, Tnode r){
		if(l==null && r==null)
			return true;
		if(l==null || r==null || l.value!=r.value)
			return false;
		return checkMirror(l.left,r.right) && checkMirror(l.right, r.left);
	}
	
	public  Tnode getLCA(Tnode node, Tnode one, Tnode two){
		if(one==null || two==null)
			return null;
		if(node==null)
			return null;
		if(node==one || node==two)
			return node;
		Tnode l=getLCA(node.left,one,two);
		Tnode r=getLCA(node.right,one,two);
		if(l!=null && r!=null)
			return node;
		if(l!=null)
			return l;
		if(r!=null)
			return r;
		return null;

	}
	
	/*public Tnode getBinarySum(Tnode node, int partial){
		if(node==null){
			val=val+partial;
		}
		
	}*/
	public int getBinarySum(Tnode node, int partial){
		if(node==null){
			return partial;
		}
		partial=2*partial+node.value;
		int leftSum=0;
		int rightSum=0;
		if(node.left==null && node.right==null)
			return partial;
		if(node.left!=null)
			leftSum=getBinarySum(node.left,partial);
		if(node.right!=null)
			rightSum=getBinarySum(node.right,partial);
		
		return leftSum+rightSum;
		
	}
	public boolean getSum(Tnode node, int partial, int K){
		if(node==null && partial==K)
			return true;
		if(node==null)
			return false;
		boolean left=getSum(node.left,partial+node.value,K);
		boolean right=getSum(node.right,partial+node.value,K);
		
		if(left || right)
			return true;
		return false;
	}
	
	public void inOrderTraversalIterative(Tnode node){
		Tnode prev=null;
		Tnode cur=node;
		while(true){
			if(cur==null && prev==node)
				break;
			else if(cur==null){
				cur=prev.parent;
			}
			else if(cur.parent==prev && cur.left==null){
				System.out.print(cur.value+ " ");
				prev=cur;
				cur=cur.right;
			}
			else if(prev==null || cur.parent==prev){
				prev=cur;
				cur=cur.left;
			}
			else if(cur.right==prev){
				prev=cur;
				cur=cur.parent;
			}
			else if(cur.left==prev){
				System.out.print(cur.value+ " ");
				prev=cur;
				cur=cur.right;
			}
		}
	}
	
	public void postOrderTraversalInterative(Tnode node){
		Tnode prev=null;
		Tnode cur=node;
		Stack<Tnode> s=new Stack<Tnode>();
		s.push(cur);
		while(!s.isEmpty()){
			cur=s.peek();
			//going down
			if(prev==null || prev.left==cur || prev.right==cur){
				if(cur.left!=null)
					s.push(cur.left);
				else if(cur.right!=null)
					s.push(cur.right);
				else{
					System.out.print(cur.value+ " ");
					s.pop();
				}
					
				
			}
			
			else if(cur.left==prev){
				if(cur.right!=null)
					s.push(cur.right);
				else{
					//System.out.print(cur.value+ " ");
					s.pop();
				}
			}
			
			else if(cur.right==prev){
				//System.out.print(cur.value+ " ");
				s.pop();
			}
			prev=cur;
			
		}
	}
	
	public Tnode preOrderTraversalwithNulls(String[] pre){
		int[] curval=new int[1];
		curval[0]=0;
		Tnode node= preOrderTraversalwithNullsUtil(pre,curval);
		levelOrderTraversal2(node);
		return node;
	}
	public Tnode preOrderTraversalwithNullsUtil(String[] pre,int[] curval){
		if(curval[0]>=pre.length)
			return null;
		if(pre[curval[0]].equals("null"))
		{
			curval[0]++;
			return null;
		}
		Tnode node=new Tnode(Integer.parseInt(pre[curval[0]]));
		curval[0]++;
		node.left=preOrderTraversalwithNullsUtil(pre,curval);
		node.right=preOrderTraversalwithNullsUtil(pre,curval);
		return node;
	}
	
	public Tnode findLCA(Tnode n1, Tnode n2){
		Set<Tnode> s=new HashSet<Tnode>();
		Tnode c1=n1;
		Tnode c2=n2;
		while(true){
			Tnode p1=c1.parent;
			Tnode p2=c2.parent;
			if(p1==null || p2==null)return null;
			if(s.contains(p1))return p1;
			if(s.contains(p2))return p2;
			s.add(p2);
			s.add(p1);
		}
	}
}
